Mybells's Log

# 4. 算法和流程控制

  1. 代码的整体结构是影响运行速度的主要因素之一。代码数量少并不意味着运行速度就快，代码数量多也不意味着运行速度一定慢。代码的组织结构和解决具体问题的思路是影响代码性能的主要因素。
  2. js提供的四种循环类型中，只有for-in循环比其他几种明显要慢。（for..in..,while,do...while,for）
  3. 提高循环的性能：
  • 只查找一次属性，并把值存到一个局部变量，然后在控制条件中使用这个变量。
  • 在js中，倒序循环会略微提升性能
for(var i=item.length;i--;){}
1
  1. 减少迭代次数
  • 限制循环迭代次数的模式被称为‘达夫设备（Duff's Device）’
var iterations=Math.floor(items.length)/8,
startAt=items.length%8,
i=0;

do{
  swith(startAt){
    case 0:process(items[i++]);
    case 1:process(items[i++]);
    case 2:process(items[i++]);
    case 3:process(items[i++]);
    case 4:process(items[i++]);
    case 5:process(items[i++]);
    case 6:process(items[i++]);
    case 7:process(items[i++]);
  }
  strartAt=0;
}while(iterarions--);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

去掉switch可以稍快

var i=items.length%8;
t=0;
while(i--){
  process(items[t++])
}
i=Math.floor(items.length/8);

while(i--){
  process(items[t++]);
  process(items[t++]);
  process(items[t++]);
  process(items[t++]);
  process(items[t++]);
  process(items[t++]);
  process(items[t++]);
  process(items[t++]);
}
//尽管用两次循环代替之前的一次循环，但它移除子循环体中的switch语句，速度比原始循环更快。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  1. 在所有情况下，基于循环的迭代比基于函数的迭代快8倍，因此在运行速度要求严格时，基于函数的迭代不是合适的选择。
  2. 条件数量越大，越倾向于使用switch而不是if-else。循环条件较少时if-else更易读，当条件数量较多时switch更易读。
  3. 大多数情况下switch比if-else运行的要快，但只有当条件数量很大时才快的明显。这两个语句主要性能区别是:当条件增加时，if-else性能负担增加的程度比switch要多。
  4. 优化if-else,最简单的优化方法是确保最可能出现的条件放在首位。应该按照最最大概率到最小概率的顺序排列，以确保运行速度最快。
  5. 为了最小化条件判断的次数，代码可重写为一系列嵌套的if-else的语句。
if(value<3){
  if(value==0){

  }else if(){

  }
} else {
  if(){

  }else if(){

  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
  1. 当你使用查找表时，必须要完全抛弃条件判断语句。这个过程变成数组项查询或者对象成员查询。查找表的一个主要优点是：不用书写任何条件判断语句，即便候选值数量增加时，也几乎不会产生额外的性能开销。
  2. 最常见的导致栈溢出的原因是不正确的终止条件，因此定位模式错误的第一步是验证终止条件。如果终止条件没问题，那么可能是算法中包含了太多层递归，为了能在浏览器中安全的工作，建议改用迭代、Memoization或者结合两者使用。
  • 迭代
//合并排序
function mergeSort(items){
  if(items.length==1){
    return items;
  }
  var middle=Math.floor(items.length/2),
  left=items.slice(0,middle),
  right=items.slice(middle);
  return merge(mergeSort(left),mergeSort(right));
}

function merge(left,right){
  var result=[];

  while(left.length>0 && right.length>0){
    if(left[0]>right[0]){
      result.push(left.shift());
    }else{
      result.push(right.shift());
    }
  }

  return result.concat(left).concat(right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

尽管迭代版本的合并排序算法比递归实现要慢一些，但它不会像递归版本那样受调用栈限制的影响。把递归算法改用迭代是避免栈溢出错误的方法之一。

  • Memoization

减少工作量就是最好的性能优化技术。代码要处理的事越少，它的运行速度就越快。Memoization正是一种避免重复工作的方法，它缓存前一个计算结果供后续计算使用，避免了重复工作。这使得它成为递归算法中有用的技术。

function memoize(fundamental,cache){
  cache=cache||{};
  var shell=function(arg){
    if(!cache.hasOwnProperty(arg)){
      cache[arg]=fundamental(arg);
    }
    return cache[arg];
  }
  return shell;
}
1
2
3
4
5
6
7
8
9
10
  1. 由于js是解释性语言，与编译语言不同的是，它无须编译，而是将代码以字符串的形式交给js引擎来执行。因此，代码性能在一定程度上取决于客户端浏览器的javascript引擎。

← 5. 字符串和正则表达式 →